package solution;

import common.ListNode;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-21 14:28
 */
public class Solution_7math {

    /*===========================================================================================================================
     * 位运算1 191. 位1的个数--汉明重量
     * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
     * n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止。
     * */
    public int hammingWeight(int n) {
        int res=0;
        while (n!=0){
            n=n&(n-1);
            res++;
        }
        return res;
    }
    //把n往右移32次，每次都和1进行与运算
    public int hammingWeight1(int n) {
        int cnt=0;
        while (n!=0){
            cnt+=n&1;
            n=n>>>1;
        }
        return cnt;
    }

    /*===========================================================================================================================
     * 位运算2 汉明距离
     * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
     * 先异或运算，然后再计算这个异或运算的结果在二进制表示中1的个数
     * */
    public int hammingDistance(int x, int y) {
        int yh=x^y;
        return Integer.bitCount(yh);
    }

    /*===========================================================================================================================
     * 位运算3 231. 2 的幂
     * 一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
     * */
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }

    /*===========================================================================================================================
     * 位运算4 136. 只出现一次的数字
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算的结果为它本身
     * */
    public int singleNumber(int[] nums) {
        int res=0;
        for (int n:nums) {
            res^=n;
        }
        return res;
    }

    /*===========================================================================================================================
     * 位运算4 268. 丢失的数字
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
     * 方法1：只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下
     * */
    public int missingNumber1(int[] nums) {
        int n=nums.length;
        int res=0;
        res^=n;
        // 和其他的元素、索引做异或
        for (int i = 0; i < n; i++) {
            res^=i^nums[i];
        }
        return res;
    }
    //方法2：直接用数组判断
    public int missingNumber2(int[] nums) {
        int n=nums.length;
        boolean[] isExist=new boolean[n+1];
        for (int i = 0; i < n; i++) {
            isExist[nums[i]]=true;
        }
        int i=0;
        while (i<isExist.length){
            if (!isExist[i])
                break;
            i++;
        }
        return i;
    }

    //方法3：等差数列求和公式，现在有个等差数列 0, 1, 2,…, n，其中少了某一个数字，请你把它找出来。那这个数字不就是 sum(0,1,..n) - sum(nums) 嘛
    public int missingNumber3(int[] nums) {
        int n=nums.length;
        int sum1=(0+n)*(n+1)/2;
        int sum2=0;
        for (int x:nums) {
            sum2+=x;
        }
        return sum1-sum2;
    }
    public int missingNumber(int[] nums) {
        //考虑溢出，我们让每个索引减去其对应的元素，再把相减的结果加起来，不就是那个缺失的元素吗？
        int n=nums.length;
        int res=0;
        res+=n-0;
        for (int i = 0; i < n; i++) {
            res+=(i-nums[i]);
        }
        return res;
    }

    /*===========================================================================================================================
     * 645. 错误的集合
     * 集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
     * 给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
     * 思路：通过将每个索引对应的元素变成负数，以表示这个索引被对应过一次了：
     * */
    public int[] findErrorNums(int[] nums) {
        int n=nums.length;
        int dup=-1;
        for (int i = 0; i < n; i++) {
            //元素从1开始
            int index=Math.abs(nums[i])-1;
            // nums[index] 小于 0 则说明重复访问
            if (nums[index]<0)
                dup=Math.abs(nums[i]);
            else
                nums[index]*=-1;
        }
        int miss=-1;
        for (int i = 0; i < n; i++) {
            // nums[i] 大于 0 则说明没有访问
            if (nums[i]>0)
                // 将索引转换成元素
                miss=i+1;
        }
        return new int[]{dup,miss};
    }

    /*===========================================================================================================================
     * 阶乘1 172. 阶乘后的零
     * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
     * 思路：两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，n! 最多可以分解出多少个因子 2 和 5，这个主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。
     * 现在，问题转化为：n! 最多可以分解出多少个因子 5？
     * 将1到n的每个5的倍数，循环除以5
     * */
    public int trailingZeroes(int n) {
        int res=0;
        for (int i = 5; i <=n ; i+=5) {
            int cur=i;
            while (cur%5==0){
                res++;
                cur/=5;
            }
        }
        return res;
    }

    long trailingZeroes(long n) {
        long res = 0;
        for (long d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }
    /*===========================================================================================================================
     * 阶乘2 793. 阶乘函数后 K 个零
     * f(x) 是 x! 末尾是 0 的数量。（回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 ）,给定 K，找出多少个非负整数 x ，能满足 f(x) = K 。
     * 思路：二分查找，f(x)随着x单调递增
     * */
    long left_bound(int target){
        long left= 0,right=Long.MAX_VALUE;
        while (left<right){
            long mid=left+(right-left)/2;
            if (trailingZeroes(mid)>=target){
                //此时阶乘后的0过多，mid过大
                right=mid;
            }else if (trailingZeroes(mid)<target){
                left=mid+1;
            }
        }
        return left;
    }
    long right_bound(int target){
        long left= 0,right=Long.MAX_VALUE;
        while (left<right){
            long mid=left+(right-left)/2;
            if (trailingZeroes(mid)>target){
                //此时阶乘后的0过多，mid过大
                right=mid;
            }else if (trailingZeroes(mid)<=target){
                left=mid+1;
            }
        }
        return left-1;
    }
    public int preimageSizeFZF(int k) {
        return (int)(right_bound(k)-left_bound(k)+1);
    }

    /*===========================================================================================================================
     * 素数  204. 计数质数
     * 统计所有小于非负整数 n 的质数的数量。
     * 埃氏筛：先初始化一个数组，全部为质数，从2开始，将所有质数的x倍标记为合数
     * */
    public int countPrimes(int n) {
        boolean[] isPrimes=new boolean[n];
        Arrays.fill(isPrimes,true);
        if (n<=1)
            return 0;
        int count=0;
        for (int i = 2; i*i < n; i++) {
            if (isPrimes[i])
                for (int j = i*i; j < n; j+=i) {
                    isPrimes[j]=false;
                }
        }
        for (int i = 2; i < n; i++) {
            if (isPrimes[i]) count++;
        }
        return count;
    }

    /*===========================================================================================================================
     * 幂运算1 372. 超级次方
     * 你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
     * 1、处理数组形式的b  --递归 superPow(a, [1,5,6,4])=(a^4)*superPow(a,[1,5,6])^10
     * 2、如何得到求模之后的结果  --(a * b) % k = (a % k)(b % k) % k
     * 3、如何高效进行幂运算
     * */
    // 计算 a 的 k 次方的结果然后与 1337 求模的结果
    int mypow(int a, int k){
        if(k==0) return 1;
        a%=1337;
        if (k%2==1){
            // k 是奇数
            return (a*mypow(a,k-1))%1337;
        }else {
            int sub=mypow(a,k/2);
            return (sub*sub)%1337;
        }
    }
    public int superPow(int a, int[] b) {
        if (b.length==0) return 1;
        int n=b.length;
        int last=b[n-1];
        int[] bremoveLast=new int[n-1];
        for (int i = 0; i < n-1; i++) {
            bremoveLast[i]=b[i];
        }
        int part1=mypow(a,last);
        int part2=mypow(superPow(a,bremoveLast),10);
        return (part1*part2)%1337;

    }

    /*===========================================================================================================================
     * 幂运算2   3的幂
     * 1.循环
     * 2.题中n的范围是-2^31 <= n <= 2^31 - 1，而在这个范围内3的最大幂是1162261467，在比他大就超过int表示的范围了，我们直接用它对n求余即可，过求余的结果是0，说明n是3的幂次方
     * */
/*    public boolean isPowerOfThree(int n) {
        if (n<1)
            return false;
        while (n%3==0) {
            n=n/3;
        }
        return n==1;
    }*/
    public boolean isPowerOfThree(int n) {
        return (n>0&&1162261467%n==0);
    }
    /*===========================================================================================================================
     *Fizz Buzz
     * */
    public List<String> fizzBuzz(int n) {
        List<String> list=new LinkedList<>();
        for (int i = 1; i <=n; i++) {
            String s=getStringn(i);
            list.add(s);
        }
        return list;
    }

    public String getStringn(int n){
        StringBuffer s=new StringBuffer();
        if (n%3==0){
            s.append("Fizz");
        }
        if (n%5==0)
            s.append("Buzz");
        if (s.length()==0)
            s.append(n);
        return s.toString();
    }


    /*===========================================================================================================================
     * 随机抽取1  382. 链表随机节点
     * 给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
     * 水塘抽样算法:当你遇到第 i 个元素时，应该有 1/i 的概率选择该元素，1 - 1/i 的概率保持原有的选择
     * */
    class Solution382 {
        ListNode head;

        public Solution382(ListNode head) {
            this.head=head;
        }

        public int getRandom() {
            Random random=new Random();
            int i=0,res=0;
            ListNode p=head;
            while (p!=null){
                i++;
                // 生成一个 [0, i) 之间的整数
                // 这个整数等于 0 的概率就是 1/i
                if (random.nextInt(i)==0){
                    res=p.val;
                }
                p=p.next;
            }
            return res;
        }
    }

    /*===========================================================================================================================
     * 随机抽取2  398. 随机数索引
     * 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
     * 只在判断到target时开始随机
     * */
    class Solution {
        int[] nums;
        int n;
        public Solution(int[] nums) {
            this.nums=nums;
            n=nums.length;
        }

        public int pick(int target) {
            Random random=new Random();
            int i=0,res=0;
            for (int j = 0; j < n; j++) {
                int num=nums[j];
                if (num==target){
                    i++;
                    if (random.nextInt(i)==0){
                        res=j;
                    }
                }
            }
            return res;
        }
    }

    /*===========================================================================================================================
     * 一行代码解决问题1  292. Nim 游戏
     * 你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。
     * 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
     * 我们发现只要踩到 4 的倍数，就落入了圈套，永远逃不出 4 的倍数，而且一定会输。
     * */
    public boolean canWinNim(int n) {
        // 如果上来就踩到 4 的倍数，那就认输吧
        // 否则，可以把对方控制在 4 的倍数，必胜
        return n%4!=0;
    }

    /*===========================================================================================================================
     * 一行代码解决问题2  877. 石子游戏
     * 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
     * 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
     * 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
     * 先手必胜，一是石头总共有偶数堆，石头的总数是奇数，把石头按索引的奇偶分为两组，那么这两组石头的数量一定不同，也就是说一堆多一堆少。因为石头的总数是奇数，不能被平分。
     * 而作为第一个拿石头的人，你可以控制自己拿到所有偶数堆，或者所有的奇数堆。
     * */
    boolean stoneGame(int[] piles) {
        return true;
    }


    /*===========================================================================================================================
     * 一行代码解决问题2  319. 灯泡开关
     * 初始时有 n 个灯泡处于关闭状态。对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
     * 第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。第 2 轮，每两个灯泡切换一次开关。 即，每两个灯泡关闭一个。第 3 轮，每三个灯泡切换一次开关。第 i 轮，每 i 个灯泡切换一次开关。 而第 n 轮，你只切换最后一个灯泡的开关。
     * 找出 n 轮后有多少个亮着的灯泡。
     * 思路：因为电灯一开始都是关闭的，所以某一盏灯最后如果是点亮的，必然要被按奇数次开关。
     * */
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }




    /*===========================================================================================================================
     *罗马数字转整数
     * */
    public int romanToInt(String s) {
        Map<String,Integer> map=new HashMap<>();
        map.put("I", 1);
        map.put("IV", 4);
        map.put("V", 5);
        map.put("IX", 9);
        map.put("X", 10);
        map.put("XL", 40);
        map.put("L", 50);
        map.put("XC", 90);
        map.put("C", 100);
        map.put("CD", 400);
        map.put("D", 500);
        map.put("CM", 900);
        map.put("M", 1000);
        int res=0;
        for (int i = 0; i < s.length();) {
            if (i+1<s.length()&&map.containsKey(s.substring(i,i+2))){
                res+=map.get(s.substring(i,i+2));
                i+=2;
            }else {
                res+=map.get(s.substring(i,i+1));
                i++;
            }
        }
        return res;
    }





    public static void main(String[] args) {

        Solution_7math object=new Solution_7math();
//        List<String> res=object.fizzBuzz(15);
//        System.out.println(res);
//        System.out.println(object.countPrimes(10));
//        System.out.println(object.isPowerOfThree(27));
        System.out.println(object.romanToInt("III"));

    }
}
